//#include<bits/stdc++.h>
//using namespace std;
//#define int long long
//const int MAXN = 2e3 + 10;
//const int MAXM = 6e3 + 10;
//int n, m;
//struct Edge {
//	int to, w, next;
//} edge[MAXM]; // 链式前向星存图
//int head[MAXN], tot;
//inline void Init()
//{
//	for (int i = 0; i < MAXM; i++) {
//		edge[i].next = 0;
//	}
//	for (int i = 0; i < MAXN; i++) {
//		head[i] = 0;
//	}
//	tot = 0;
//}
//inline void addedge(int u, int v, int w)
//{
//	edge[++tot].to = w;
//	edge[tot].w = w;
//	edge[tot].next = head[u];
//	head[u] = tot;
//}
//queue<int> q;
//int dis[MAXN], vis[MAXN], cnt[MAXN];
//bool spfa()
//{
//	while(!q.empty()) q.pop();
//	memset(dis, 0x3f, sizeof(dis));
//	memset(vis, 0, sizeof(vis));
//	memset(cnt, 0, sizeof(cnt));
//	dis[1] = 0;
//	vis[1] = true;
//	q.push(1);
//	while (!q.empty()) {
//		int x = q.front();
//		q.pop();
//		vis[x] = false;
//		for (int i = head[x]; i; i = edge[i].next) {
//			int y = edge[i].to, z = edge[i].w;
//			if (dis[y] > dis[x] + z) {
//				dis[y] = dis[x] + z;// 更新最短路
//				cnt[y] = cnt[x] + 1;// 更新包含边数
//				if (cnt[y] >= n) {// WA 忘记等号
//					return true;
//				}
//				if (! vis[y]) {
//					q.push(y);
//					vis[y] = true;
//				}
//			}
//		}
//	}
//	return false;
//}
//signed main()
//{
//	int T;
//	cin >> T;
//	while (T --) {
//		Init();
//
//		cin >> n >> m;
//		for (int i = 1; i <= m; i++) {
//			int u, v, w;
//			cin >> u >> v >> w;
//			addedge(u, v, w);
//			if (w >= 0) {
//				addedge(v, u, w);
//			}
//		}
//
//		if (spfa()) {
//			cout << "YES";
//		} else {
//			cout << "NO";
//		}
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//using namespace std;
//
//const int INF = INT_MAX;
//
//struct Edge {
//	int u, v, w;
//};
//
//bool findNegativeCycle(int n, vector<Edge>& edges)
//{
//	vector<int> dist(n + 1, INF); // 距离数组，初始化为无穷大
//	dist[1] = 0; // 顶点1的距离初始化为0
//
//	// 进行n-1次松弛操作
//	for (int i = 1; i <= n - 1; ++i) {
//		// 遍历所有边进行松弛操作
//		for (const auto& edge : edges) {
//			int u = edge.u;
//			int v = edge.v;
//			int w = edge.w;
//
//			// 如果能通过当前边更新顶点的最短路径距离，则进行更新
//			if (dist[u] != INF && dist[u] + w < dist[v]) {
//				dist[v] = dist[u] + w;
//			}
//		}
//	}
//
//	// 再进行一次松弛操作，如果存在距离更新，则存在负环
//	for (const auto& edge : edges) {
//		int u = edge.u;
//		int v = edge.v;
//		int w = edge.w;
//
//		if (dist[u] != INF && dist[u] + w < dist[v]) {
//			return true; // 存在负环
//		}
//	}
//
//	return false; // 不存在负环
//}
//
//int main()
//{
////	输入
//	int T;
//	cin >> T;
//
//	while (T--) {
//		int n, m;
//		cin >> n >> m;
//
//		vector<Edge> edges(m);
//		for (int i = 0; i < m; ++i) {
//			cin >> edges[i].u >> edges[i].v >> edges[i].w;
//		}
//		//计算
//		if (findNegativeCycle(n, edges)) {
//			cout << "YES" << endl;
//		} else {
//			cout << "NO" << endl;
//		}
//	}
//
//	return 0;
//}//WA
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Edge {
	int source, target, weight;
};

// Bellman-Ford 算法
bool bellmanFord(vector<Edge>& edges, vector<int>& dist, int n, int s)
{
	dist[s] = 0;
	for (int i = 1; i < n; ++i) {
		for (const auto& edge : edges) {
			int u = edge.source;
			int v = edge.target;
			int w = edge.weight;
			if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
			}
		}
	}

	// 检查负环
	for (const auto& edge : edges) {
		int u = edge.source;
		int v = edge.target;
		int w = edge.weight;
		if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
			return false; // 存在负环
		}
	}

	return true;
}

// Dijkstra 算法
void dijkstra(vector<vector<int>>& graph, vector<int>& dist, int s)
{
	int n = graph.size();
	vector<bool> visited(n, false);
	dist[s] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(dist[s], s));

	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		visited[u] = true;

		for (int v = 0; v < n; ++v) {
			int w = graph[u][v];
			if (w != INT_MAX && !visited[v] && dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				pq.push(make_pair(dist[v], v));
			}
		}
	}
}

void johnson(vector<Edge>& edges, int n)
{
	edges.push_back({n, 0, 0}); // 添加一个新的源节点，与其他节点之间的边权为0

	vector<int> h(n + 1, 0); // 用于 Bellman-Ford 算法中的顶点权值调整
	vector<int> dist(n + 1, INT_MAX); // 存储顶点对之间的最短路径长度

	// 使用 Bellman-Ford 算法计算顶点权值调整值
	if (!bellmanFord(edges, h, n + 1, n)) {
		cout << -1 << endl; // 存在负环，输出-1
		return;
	}

	// 根据顶点权值调整值重新计算边权值
	for (auto& edge : edges) {
		edge.weight = edge.weight + h[edge.source] - h[edge.target];
	}

	// 使用 Dijkstra 算法计算所有节点对之间的最短路径
	vector<vector<int>> shortestPaths(n, vector<int>(n, INT_MAX));
	for (int i = 0; i < n; ++i) {
		vector<int> dist(n, INT_MAX);
		dijkstra(shortestPaths, dist, i);

		for (int j = 0; j < n; ++j) {
			shortestPaths[i][j] = dist[j];
		}
	}

	// 根据顶点权值调整值恢复最短路径长度
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			shortestPaths[i][j] = shortestPaths[i][j] - h[i] + h[j];
		}
	}

	// 输出结果
	for (int i = 0; i < n; ++i) {
		long long sum = 0;
		for (int j = 0; j < n; ++j) {
			if (shortestPaths[i][j] == INT_MAX) {
				sum += 1000000000LL; // 若不存在路径则设为10^9
			} else {
				sum += (j + 1) * (long long)shortestPaths[i][j];
			}
		}
		cout << sum << endl;
	}
}
int main()
{
	int n, m;
	cin >> n >> m;

	vector<Edge> edges;
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		edges.push_back({u, v, w});
	}

	johnson(edges, n);

	return 0;
}
